The economy of scale provided by cloud computing has attracted many corporations to outsource their applications to cloud data center (CDC) providers. The uncertainty of arriving tasks makes it a big challenge for private CDC to cost effectively schedule delay-bounded tasks without exceeding their respective delay bounds. See A. Beloglazov, J. Abawajy, and R. Buyya, “Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing,” Future Generation Computer Systems, vol. 28, no. 5, pp. 755-768, May 2012; K. M. Sim, “Complex and concurrent negotiations for multiple interrelated e-Markets,” IEEE Transactions on Cybernetics, vol. 43, no. 1, pp. 230-245, February 2013; O. S. Gedik, and A. A. Alatan, “3-D rigid body tracking using vision and depth sensors,” IEEE Transactions on Cybernetics, vol. 43, no. 5, pp. 1395-1405, October 2013; and O. Lopes, M. Reyes, S. Escalera, and J. Gonzalez, “Spherical blurred shape model for 3-D object and pose recognition: quantitative analysis and HCI applications in smart environments,” IEEE Transactions on Cybernetics, vol. 44, no. 12, pp. 2379-2390, December 2014, each incorporated herein by reference in its entirety.
In cloud computing, typical Infrastructure as a Service (IaaS) providers such as Rackspace provide resources to support applications delivered to users. See Z. Ou, H. Zhuang, A. Lukyanenko, J. K. Nurminen, P. Hui, V. Mazalov, and A. Yla-Jaaski, “Is the Same Instance Type Created Equal? Exploiting Heterogeneity of Public Clouds,” IEEE Trans. Cloud Comput., vol. 1, no. 2, pp. 201-214, July 2013, incorporated herein by reference in its entirety. The work in Zuo (see X. Zuo, G. scheduling for hybrid IaaS cloud,” IEEE Transactions Automation Science and Engineering, vol. 11, no. 2, pp. 564-573, April 2014, incorporated herein by reference in its entirety) is from the perspective of a typical IaaS provider.
A private CDC as described herein refers to a resource-limited IaaS provider that may schedule some tasks to external public clouds if its resources cannot guarantee the expected QoS. The consideration of security and regulation may also suggest that some applications be provided by a private CDC only.
One private CDC objective is to provide services to all arriving tasks from millions of users in the most cost-effective way, while also ensuring user-defined delay bounds. The arrival of user tasks can be aperiodic and uncertain, and therefore it is challenging for a private CDC to accurately predict the upcoming tasks. In addition, the limitation of resources in a private CDC may require that some arriving tasks be refused in order to provide delay assurance of already-accepted tasks when the number of arriving tasks is unexpectedly large. See L. Wu, S. K. Garg, and R. Buyya, “SLA-based admission control for a software-as-a-service provider in cloud computing environments,” J. Comput. Syst. Sci., vol. 78, no. 5, pp. 1280-1299, September 2012 and J. Luo, L. Rao, and X. Liu, “Temporal load balancing with service delay guarantees for data center energy cost optimization,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 3, pp. 775-784, March 2014, each incorporated herein by reference in its entirety. However, this reduces the throughput of a private CDC and inevitably can bring a large penalty due to the refusal of tasks.
The emergence of hybrid clouds enables a private CDC to outsource some of its arriving tasks to public clouds when incoming tasks unexpectedly peak. In hybrid clouds, the total cost of a private CDC primarily includes the energy cost caused by the accepted tasks executed in it, and the execution cost of tasks dispatched to public clouds.
Public clouds (e.g., Amazon EC2) deliver dynamic resources to users by creating a set of virtual machines (VMs). Delay-bounded tasks usually have user-defined delay bounds to satisfy. In a real-life market, the execution price of VM instances provided by public clouds varies with the delay bounds. See H. Xu and B. Li, “Dynamic cloud pricing for revenue maximization,” IEEE Transactions Cloud Computing, vol. 1, no. 2, pp. 158-171, July 2013, incorporated herein by reference in its entirety.
The energy price of a private CDC tends to exhibit temporal diversity. Minimizing the total cost of a private CDC in hybrid clouds where the execution and energy prices exhibit a temporal diversity becomes a challenging problem.
Resource provisioning in CDCs attempts to provision limited resources, while also guaranteeing the performance of user tasks. A number of methods on resource provisioning in CDCs has been proposed. See W. Tian, Y. Zhao, M. Xu, Y Zhong, and X. Sun, “A toolkit for modeling and simulation of real-time virtual machine allocation in a cloud data center,” IEEE Trans. Autom. Sci. Eng., vol. 12, no. 1, pp. 153-161, January 2015; Z. Xiao, W. Song, and Q. Chen, “Dynamic resource allocation using virtual machines for cloud computing environment,” IEEE Transactions Parallel and Distributed Systems, vol. 24, no. 6, pp. 1107-1117, June 2013; T. Lu, M. Chen, and L. Andrew, “Simple and effective dynamic provisioning for power-proportional data centers,” IEEE Transactions Parallel and Distributed Systems, vol. 24, no. 6, pp. 1161-1171, June 2013; and O. Beaumont, L. Eyraud-Dubois, C. Thraves Caro, and H. Rejeb, “Heterogeneous resource allocation under degree constraints,” IEEE Transactions Parallel and Distributed Systems, vol. 24, no. 5, pp. 926937, May 2013, each incorporated herein by reference in its entirety. In Tian, a lightweight system is designed to simulate real-time resource provisioning in CDCs. In Xiao, a virtualized system is presented to dynamically provision resources based on users' tasks. In Lu, the effect of workload prediction on resource provisioning is investigated. Then, a decentralized algorithm that attempts to dynamically provision resources is proposed. In Beaumont, the problem of distributing user tasks to multiple heterogeneous servers is considered. Several heuristic algorithms are proposed to realize the online allocation. However, none of the existing studies focus on resource provisioning for delay-bounded tasks in hybrid clouds.
Task scheduling in CDCs is a challenging problem that has been previously investigated. In Fard, an algorithm to dispatch scientific workflow tasks in multiple cloud environments is presented. See H. Fard, R. Prodan, and T. Fahringer, “A truthful dynamic workflow scheduling mechanism for commercial multicloud environments,” IEEE Transactions Parallel and Distributed Systems, vol. 24, no. 6, pp. 12031212, June 2013, incorporated herein by reference in its entirety. In Calheiros, an algorithm that can smartly exploit idle time of resources and replicate tasks is proposed. See R. Calheiros and R. Buyya, “Meeting deadlines of scientific workflows in public clouds with tasks replication,” IEEE Transactions Parallel and Distributed Systems, vol. 25, no. 7, pp. 1787-1796, July 2014, incorporated herein by reference in its entirety. Workflow applications whose deadlines are soft can fully take advantage of this algorithm and mitigate the performance degradation caused by variation of resources. In Agrawal, three algorithms that attempt to realize energy-aware task scheduling are proposed and compared with the existing scheduling algorithms. See P. Agrawal and S. Rao, “Energy-aware scheduling of distributed systems,” IEEE Trans. Autom. Sci. Eng., vol. 11, no. 4, pp. 1163-1175, October 2014, incorporated herein by reference in its entirety. In Zuo, a task scheduling method based on heuristics is proposed to maximize the profit of a private cloud while ensuring the delay bounds. However, none of the cited studies considers the temporal diversity in the execution and energy prices in hybrid clouds.
In Luo, a two-stage system is presented to dynamically dispatch arriving tasks to execute in CDCs and to minimize the energy cost of CDCs. However, it simply trims arriving tasks to satisfy the schedulability condition. Therefore, the refused tasks caused by this strategy may bring a large penalty to a CDC provider and decrease the system throughput.
Some recent studies that focus on performance modeling of CDCs are based on classical queueing theory. See Y. Yao, L. Huang, A. Sharma, L. Golubchik, and M. Neely, “Data centers power reduction: A two time scale approach for delay tolerant workloads,” in Proc. 2012 IEEE INFOCOM 2012, pp. 1431-1439; J. Cao, K. Hwang, K. Li, and A. Zomaya, “Optimal multiserver configuration for profit maximization in cloud computing,” IEEE Transactions Parallel and Distributed Systems, vol. 24, no. 6, pp. 1087-1096, June 2013; and J. Bi, H. Yuan, M. Tie, and W. Tan, “SLA-based optimisation of virtualised resource for multi-tier web applications in cloud data centres,” Enterprise Information Syst., vol. 9, no. 7, pp. 743-767, November 2015, each incorporated herein by reference in its entirety. In Yao, the average response time is modeled and estimated according to the queueing theory. A task scheduling algorithm is proposed next to reduce the energy cost of CDCs. In Cao, a multiserver system in a cloud is modeled as an M/M/m queueing model. Based on this model, the problem of multi-server configuration that attempts to maximize the profit of a cloud is formulated and solved analytically. In Bi, a hybrid queueing model is constructed for multi-tier applications in CDCs. Based on the model, a constrained optimization problem is formulated and solved by the proposed heuristic algorithm. The average response time is estimated and the profit maximization or cost minimization problems are formulated and solved. However, these studies can only guarantee the average response time for all tasks. In addition, the long-tail distribution of response time for the tasks implies that the delay of some tasks may be much longer than what users can accept. See G. von Laszewski, J. Diaz, F Wang, and G. Fox, “Comparison of multiple cloud frameworks,” in Proc. 2012 IEEE 5th International Conference Cloud Computing, 2012, pp. 734-741, incorporated herein by reference in its entirety.
The “background” description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as conventional art at the time of filing, are neither expressly nor impliedly admitted as conventional art against the present disclosure.